# 动态规划查找上升子序列
def lengthOfLIS(nums):
    if not nums:
        return 0

    res = 1
    dp = [1 for i in range(len(nums) + 1)]
    for i in range(len(nums)):
        for j in range(0, i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)

        res = max(res, dp[i])
    return res


# 二分查找实现最长上升子序列
def midFindLengthOfLIS(nums):
    res = []
    for i in range(len(nums)):
        index = lower_bound(res, 0, len(res), nums[i])
        if index > len(res) - 1:
            res.append(nums[i])
        else:
            res[index:len(res)] = []
            res.append(nums[i])
    return res


'''
    
'''


def lower_bound(res, start, end, num):
    if not res:
        return 0
    index = 1
    while index > 0:
        index = int((start + end) / 2)
        if index == 0:
            return index
        if res[index - 1] < num < res[index]:
            return index
        if num > res[index]:
            start = index + 1
        elif num < res[index]:
            end = index - 1
        else:
            return index
    return -1


if __name__ == '__main__':
    print(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18, 20]))
    print(midFindLengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18, 20]))
